package com.sheng.leetcode.year2022.month09.day26;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/09/26
 *<p>
 * 面试题 17.19. 消失的两个数字<p>
 *<p>
 * 给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。<p>
 * 你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？<p>
 * 以任意顺序返回这两个数字均可。<p>
 *<p>
 * 示例 1:<p>
 * 输入: [1]<p>
 * 输出: [2,3]<p>
 *<p>
 * 示例 2:<p>
 * 输入: [2,3]<p>
 * 输出: [1,4]<p>
 * 提示：<p>
 *<p>
 * nums.length <=30000<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/missing-two-lcci">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCodeMissingTwo {

    @Test
    public void test01() {
//        int[] nums = {1};
//        int[] nums = {2,3};
//        int[] nums = {1, 2, 3, 4, 6, 7, 9, 10};
        int[] nums = {1, 2, 3, 5, 7, 8, 9, 10};
        System.out.println(Arrays.toString(new Solution().missingTwo(nums)));
    }
}
// 暴力破解5ms
class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length + 2;
        int index = 0;
        int[] ints = new int[2];
        int j = 1;
        // 对数组进行排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            // 符合条件，直接返回
            if (index == 2) {
                return ints;
            }
            // 如果不相等，则执行以下操作
            while (nums[i] != j) {
                ints[index++] = j++;
            }
            j++;
        }
        // 如果循环结束依旧不满足
        while (j < n || index <= 1) {
            ints[index++] = j++;
        }
        return ints;
    }
}

//class Solution {
//    public int[] missingTwo(int[] nums) {
//        int xorsum = 0;
//        int n = nums.length + 2;
//        for (int num : nums) {
//            xorsum ^= num;
//        }
//        for (int i = 1; i <= n; i++) {
//            xorsum ^= i;
//        }
//        // 防止溢出
//        int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum));
//        int type1 = 0, type2 = 0;
//        for (int num : nums) {
//            if ((num & lsb) != 0) {
//                type1 ^= num;
//            } else {
//                type2 ^= num;
//            }
//        }
//        for (int i = 1; i <= n; i++) {
//            if ((i & lsb) != 0) {
//                type1 ^= i;
//            } else {
//                type2 ^= i;
//            }
//        }
//        return new int[]{type1, type2};
//    }
//}
//
//作者：LeetCode-Solution
//链接：https://leetcode.cn/problems/missing-two-lcci/solution/xiao-shi-de-liang-ge-shu-zi-by-leetcode-zuwq3/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
